#coding:utf8
'''
1,2,3 -> 1,3,2
3,2,1 -> 1,2,3

8,7,3,4,2,1
先找到3
然后把后面的从后往前找到第一个大于3的值，
把它和三对换
然后把后面的重新拍序
874321

8735412 -> 8735421
8735421 -> 8741235
8734521 -> 8735124
8754321 -> 1234578
'''

class Solution(object):
    def nextPermutation(self, nums):
        j = -1
        for i in range(len(nums)-1,0,-1):
            if nums[i-1] < nums[i]:
                j = i-1
                break
        for i in range(len(nums)-1,-1,-1):
            if nums[i] > nums[j]:
                nums[i],nums[j] = nums[j],nums[i]
                nums[j+1:] = sorted(nums[j+1:])
                return

s = Solution()
nums = [8,7,3,5,4,1,2]
s.nextPermutation(nums)
s.nextPermutation(nums)
print nums
nums = [8,7,3,4,5,2,1]
s.nextPermutation(nums)
print nums
nums = [8,7,5,4,3,2,1]
s.nextPermutation(nums)
print nums
